#include <stdio.h>
#include <string.h>
#include <math.h>
#define MAX 50005



int tq[MAX], tq2[MAX];

int shu[50005];
int n;

main()
{
//	freopen("input","r",stdin);
	int icase, ncase,i, j; 
	int tot ,max;
	scanf("%d", &ncase);
	for (icase=1;icase<=ncase;icase++)
	{
		memset(tq,0,sizeof(tq));
		memset(tq2,0,sizeof(tq2));
		scanf("%d", &n);
		for (i=1;i<=n;i++) scanf("%d", &shu[i]);

		
		tq[0]=-200000000;
		tot=0;
		for (i=1; i<=n; i++)
		{
			tot+=shu[i];
			tq[i]=tot>tq[i-1] ? tot:tq[i-1];
			if (tot<0) tot=0;
		}
		tq2[n+1]=-200000000;
		tot=0;
		for (i=n;i>=1;i--)
		{
			tot+=shu[i];
			tq2[i]=tot>tq2[i+1] ? tot:tq2[i+1];
			if (tot<0) tot=0;
		}

/*		for (i=1;i<=n;i++) printf("%d ",tq[i]);
		printf("\n");
		for (i=1;i<=n;i++) printf("%d ",tq2[i]);
		printf("\n");
*/

		int max;
		max=tq[1]+tq2[2];
		for (i=1;i<n;i++) 
			if (max<tq[i]+tq2[i+1])
				max=tq[i]+tq2[i+1];
		printf("%d\n",max);

	}



	return 0;
}





